package com.hy.treeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeNodeSearchIterator {

    /**
     * 二叉树的统一迭代法
     * 之后我们发现迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。
     *
     * 其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码！
     *
     * 重头戏来了，接下来介绍一下统一写法。
     *
     * 我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
     *
     * 那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
     *
     * 如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
     *
     * @param root
     * @return
     */

    // 前序遍历
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null){
            st.push(root);
        }
        while (!st.isEmpty()){
            TreeNode node = st.peek();
            if (node != null){
                // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.pop();
                // // 添加 右  左节点（空节点不入栈） 先进后出
                if (node.right != null){
                    st.push(node.right);
                }

                if (node.left != null){
                    st.push(node.left);
                }
                // 添加  中间节点
                st.push(node);

                // 中节点访问过，但是还没有处理，加入空节点做为标记。
                st.push(null);
            }
            // 只有遇到空节点的时候，才将下一个节点放进结果集
            else {
                // 将 空节点 弹出
                st.pop();
                // 取出栈中的元素
                node = st.peek();
                st.pop();
                res.add(node.val);
            }
        }
        return res;
    }

    // 中序遍历   左中右
    public List<Integer> inorderTraversal(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        // 节点 不为空  将节点压入栈
        if (root != null){
            st.push(root);
        }
        // 循环迭代
        while (!st.isEmpty()){
            TreeNode node = st.peek();
            if (node != null){
                // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.pop();
                // 添加  右节点
                if (node.right != null){
                    st.push(node.right);
                }
                // 添加中间节点
                st.push(node);
                // 中节点访问过，但是还没有处理，加入空节点做为标记。
                st.push(null);
                // 添加 左节点
                if (node.left != null){
                    st.push(node.left);
                }
            }
            // 中节点访问过，但是还没有处理，加入空节点做为标记。null -> node
            else {
                // 将 空节点 弹出
                st.pop();
                // 重新取出栈中元素
                node = st.peek();
                st.pop();
                // 加入结果集
                res.add(node.val);
            }
        }
        return res;
    }
    // 后序遍历  左右中
    public List<Integer> postorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root!= null){
            st.push(root);
        }
        while (!st.isEmpty()){
            TreeNode node = st.peek();
            if (node != null){
                // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.pop();
                // 添加中间节点
                st.push(node);
                // 中节点访问过，但是还没有处理，加入空节点做为标记。
                st.push(null);
                // 添加 右节点
                if (node.right != null){
                    st.push(node.right);
                }
                if (node.left != null){
                    st.push(node.left);
                }
            }
            // 只有遇到空节点的时候，才将下一个节点放进结果集
            else {
                st.pop();
                // 重新取出栈中元素
                node = st.peek();
                st.pop();
                // 加入到结果集
                res.add(node.val);
            }
        }
        return res;
    }


    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeSearchIterator treeNodeSearchIterator = new TreeNodeSearchIterator();
        System.out.println("前序遍历 :"+treeNodeSearchIterator.preorderTraversal(root));
        System.out.println("中序遍历 :"+treeNodeSearchIterator.inorderTraversal(root));
        System.out.println("后序遍历 :"+treeNodeSearchIterator.postorderTraversal(root));

    }
}
